package leetcode.code2453;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution2 {
	public int destroyTargets(int[] nums, int space) {
		Map<Integer, Integer> cnt = new HashMap<>();
		Map<Integer, Integer> min = new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			int mod = num % space;
			cnt.put(mod, cnt.getOrDefault(mod, 0) + 1);
			int m = min.getOrDefault(mod, (int) 1e9 + 1);
			if (num < m) {
				min.put(mod, num);
			}
		}
		int ans = 0, size = 0;
		for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
			if (entry.getValue() > size || (entry.getValue() == size && min.get(entry.getKey()) < ans)) {
				size = entry.getValue();
				ans = min.get(entry.getKey());
			}
		}
		return ans;
	}
}
